class MaxHeap {
  constructor() {
    this.heap = [];
  }

  // 计算将一名学生加入班级后，通过率的提升量
  getGain(pass, total) {
    return (pass + 1) / (total + 1) - pass / total;
  }

  // 插入元素并维持堆结构
  push(pass, total) {
    this.heap.push([pass, total]);
    this.bubbleUp(this.heap.length - 1);
  }

  // 取出堆顶元素（增益最大的）并维持堆结构
  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }

    return top;
  }

  // 向上调整堆
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      // 如果当前元素的增益大于父元素，则交换
      if (
        this.getGain(this.heap[index][0], this.heap[index][1]) <=
        this.getGain(this.heap[parentIndex][0], this.heap[parentIndex][1])
      ) {
        break;
      }
      [this.heap[index], this.heap[parentIndex]] = [
        this.heap[parentIndex],
        this.heap[index],
      ];
      index = parentIndex;
    }
  }

  // 向下调整堆
  sinkDown(index) {
    const length = this.heap.length;
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let largestIdx = index;

      // 比较左子节点
      if (
        leftChildIdx < length &&
        this.getGain(this.heap[leftChildIdx][0], this.heap[leftChildIdx][1]) >
          this.getGain(this.heap[largestIdx][0], this.heap[largestIdx][1])
      ) {
        largestIdx = leftChildIdx;
      }

      // 比较右子节点
      if (
        rightChildIdx < length &&
        this.getGain(this.heap[rightChildIdx][0], this.heap[rightChildIdx][1]) >
          this.getGain(this.heap[largestIdx][0], this.heap[largestIdx][1])
      ) {
        largestIdx = rightChildIdx;
      }

      if (largestIdx === index) break;

      [this.heap[index], this.heap[largestIdx]] = [
        this.heap[largestIdx],
        this.heap[index],
      ];
      index = largestIdx;
    }
  }
}

function maxAverageRatio(classes, extraStudents) {
  const heap = new MaxHeap();

  // 初始化堆
  for (const [pass, total] of classes) {
    heap.push(pass, total);
  }

  // 分配额外的学生
  for (let i = 0; i < extraStudents; i++) {
    const [pass, total] = heap.pop();
    // 给这个班级增加一名学生
    heap.push(pass + 1, total + 1);
  }

  // 计算平均通过率
  let totalRatio = 0;
  for (const [pass, total] of heap.heap) {
    totalRatio += pass / total;
  }

  return totalRatio / classes.length;
}

// 示例测试
console.log(
  maxAverageRatio(
    [
      [1, 2],
      [3, 5],
      [2, 2],
    ],
    2
  )
); // 输出: 0.78333...
console.log(
  maxAverageRatio(
    [
      [2, 4],
      [3, 9],
      [4, 5],
      [2, 10],
    ],
    4
  )
); // 输出: 0.53485...
